package com.algorithms.dp;

import org.junit.Test;

import java.util.Arrays;

/**
 问题：给定n种不同面值的硬币，分别记为c[0], c[1], c[2], … c[n]，同时还有一个总金额k，编写一个函数计算出最少需要几枚硬币凑出这个金额k？
 每种硬币的个数不限，且如果没有任何一种硬币组合能组成总金额时，返回 -1。

 示例 1：

 输入：c[0]=1, c[1]=2, c[2]=5, k=12
 输出：3
 解释：12 = 5 + 5 + 2
 示例 2：

 输入：c[0]=5, k=7
 输出：-1
 解释：只有一种面值为5的硬币，怎么都无法凑出总价值为7的零钱。

 * <br>
 */
public class CoinCount {
    int GetMinCoinCountOfValueHelper(int total, int[] values, int valueIndex, int valueCount) {
        //递归的终止条件
        if (valueIndex == valueCount) {
            return -1;
        }

        int currentValue = values[valueIndex];
        int maxCount = total / currentValue;

        for (int count = maxCount; count >= 0; count --) {
            int rest = total - count * currentValue;
            // 如果rest为0，表示余额已除尽，组合完成
            if (rest == 0) {
                return count;
            }

            // 否则尝试用剩余面值求当前余额的硬币总数
            int restCount = GetMinCoinCountOfValueHelper(rest, values, valueIndex + 1, valueCount);

            // 如果后续没有可用组合
            if (restCount == -1) {
                // 如果当前面值已经为0，返回-1表示尝试失败
                if (count == 0) { return -1; }
                continue; // 否则尝试把当前面值-1
            }

            return count + restCount;
        }

        return -1;
    }


    int[] GetMinCoinCountOfValueHelper_2(int total, int[] values, int valueIndex, int valueCount) {
        //递归的终止条件
        if (valueIndex == valueCount) {
            return new int[]{-1};
        }

        int currentValue = values[valueIndex];
        int maxCount = total / currentValue;

        for (int count = maxCount; count >= 0; count --) {
            int rest = total - count * currentValue;
            // 如果rest为0，表示余额已除尽，组合完成
            if (rest == 0) {
                return fillArray(0,count,currentValue);
            }

            // 否则尝试用剩余面值求当前余额的硬币总数
            int restCount = GetMinCoinCountOfValueHelper(rest, values, valueIndex + 1, valueCount);

            // 如果后续没有可用组合
            if (restCount == -1) {
                // 如果当前面值已经为0，返回-1表示尝试失败
                if (count == 0) { return new int[]{-1}; }
                continue; // 否则尝试把当前面值-1
            }
            int[] counts = new int[count + restCount];
            fillArray(counts,0,count,currentValue);
            fillArray(counts,count,count + restCount,values[valueIndex + 1]);
            return counts;
        }

        return new int[]{0};
    }


    int[] fillArray(int startIndex,int endIndex,int value){
        int[] arrays = new int[endIndex - startIndex];
        return this.fillArray(arrays,startIndex,endIndex,value);
    }

    int[] fillArray(int[] arrays,int startIndex,int endIndex,int value){
        for(int i = startIndex;i< endIndex;i++){
            arrays[i] = value;
        }
        return arrays;
    }

    @Test
    public void GetMinCoinCountOfValue() {
        int[] values = { 5, 3 }; // 硬币面值
        int total = 12; // 总价
        int minCoinCount = GetMinCoinCountOfValueHelper(total, values, 0, 2);

        System.out.println(minCoinCount); // 输出结果
    }

    @Test
    public void GetMinCoinCountOfValue_2() {
        int[] values = { 5, 3 }; // 硬币面值
        int total = 1; // 总价
        int[] minCoinCount = GetMinCoinCountOfValueHelper_2(total, values, 0, 2);

        System.out.println(Arrays.toString(minCoinCount)); // 输出结果
    }
}
